package lc.q101_150;

public class Q117 {

    private Node getRight(Node parent) {
        Node next = parent.next;
        while (next != null && next.left == null && next.right == null) {
            next = next.next;
        }
        if (next == null) {
            return null;
        }
        if (next.left != null) {
            return next.left;
        }
        return next.right;
    }

    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Node current = root;
        while (current != null) {
            // 找出父节点，获取下一层的子节点
            Node leftest = null;
            if (current.left != null ) {
                leftest = current.left;
            } else if (current.right != null) {
                leftest = current.right;
            } else {
                current = current.next;
                continue;
            }
            // 设置所有下一节点的值
            Node next = leftest;
            while (next != null) {
                 // 某个值;
                if (current.left != null) {
                    if (current.right != null) {
                        next.next = current.right;
                    } else {
                        next.next = getRight(current);
                        // 需要注意的是，这里的当前节点要改变
                        current = current.next;
                        while (current != null && current.left == null && current.right==null) {
                            current = current.next;
                        }
                        if (current == null) {
                            break;
                        }
                    }
                } else {// 右节点肯定不为空
                    next.next = getRight(current);
                    // 需要注意的是，这里的当前节点要改变
                    current = current.next;
                    while (current != null && current.left == null && current.right==null) {
                        current = current.next;
                    }
                    if (current == null) {
                        break;
                    }
                }
                next = next.next;
            }
            // 下一轮的父节点肯定从最左节点开始
            current = leftest;
        }
        return root;
    }
}
